class Solution:
    def splitArray(self, nums, m: int) -> int:
        a = sum(nums)
        dp = [[a + 1] * len(nums) for _ in range(m + 1)]
        dp[1][0] = nums[0]
        i = 1
        for j in range(1, len(nums)):
            dp[i][j] = dp[i][j - 1] + nums[j]

        for i in range(2, m + 1):
            for j in range(i - 1, len(nums)):
                ksum = 0
                for k in range(j, i - 2, -1):
                    ksum += nums[k]
                    dp[i][j] = min(max(ksum, dp[i - 1][k - 1]), dp[i][j])
                    if ksum >= dp[i][j]:
                        break

        return dp[-1][-1]


if __name__ == '__main__':
    so = Solution()
    num = [7, 2, 5, 10, 8]
    k = 2
    r = so.splitArray(num, k)
    print(r)
